#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <limits.h>
#include "zmalloc.h"
#include "util.h"
#include "ziplist.h"
#include "endianconv.h"
#include "redisassert.h"

#define ZIP_END 255
#define ZIP_BIGLEN 254

/* c0: 1100 0000
 * 30: 0011 0000
*/
#define ZIP_STR_MASK 0xc0
#define ZIP_INT_MASK 0x30
#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
#define ZIP_INT_16B (0xc0 | 0<<4)
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
#define ZIP_INT_24B (0xc0 | 3<<4)
#define ZIP_INT_8B 0xfe

#define ZIP_INT_IMM_MASK 0x0f
#define ZIP_INT_IMM_MIN 0xf1    /* 11110001 */
#define ZIP_INT_IMM_MAX 0xfd    /* 11111101 */
#define ZIP_INT_IMM_VAL(v) (v & ZIP_INT_IMM_MASK)

#define INT24_MAX 0x7fffff
#define INT24_MIN (-INT24_MAX - 1)

#define ZIP_IS_STR(enc) (((enc) & ZIP_STR_MASK) < ZIP_STR_MASK)

/* ZIPLIST的结构如下:
 * <zlbytes><zltail><zllen><entry><entry><zlend>
 * [uint_32][  u32 ][ u16 ][      x     ][ u8 ]
 * 对于其中的参数进行如下说明:
    * zlbytes表示ziplist占据的总字节数
    * zltail表示偏置到列表的最后一个元素 zl + zltail
    * zllen表示entry的数目
    * zlend表示255, 标志list的结尾
*/
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl) + sizeof(uint32_t))))
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl) + sizeof(uint32_t) * 2)))
#define ZIPLIST_HEADER_SIZE     (sizeof(uint32_t) * 2 + sizeof(uint16_t))
#define ZIPLIST_END_SIZE        (sizeof(uint8_t))
#define ZIPLIST_ENTRY_HEAD(zl)  ((zl) + ZIPLIST_HEADER_SIZE)
#define ZIPLIST_ENTRY_TAIL(zl)  ((zl) + intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))
#define ZIPLIST_ENTRY_END(zl)   ((zl) + intrev32ifbe(ZIPLIST_BYTES(zl)) - 1)

#define ZIPLIST_INCR_LENGTH(zl, incr) { \
    if (ZIPLIST_LENGTH(zl) < UINT16_MAX) \
        ZIPLIST_LENGTH(zl) = intrev16ifbe(intrev16ifbe(ZIPLIST_LENGTH(zl)) + incr); \
}


typedef struct zlentry {
    unsigned int prevrawlensize, prevrawlen;
    unsigned int lensize, len;
    unsigned int headersize;
    unsigned char encoding;
    unsigned char *p;
} zlentry;

/*? 获取Entry的编码方式 */
#define ZIP_ENTRY_ENCODING(ptr, encoding) do { \
    (encoding) = (ptr[0]); \
    if ((encoding) < ZIP_STR_MASK) (encoding) &= ZIP_STR_MASK; \
} while (0)

/* 根据编码方式获取整型的大小 */
static unsigned int zipIntSize(unsigned char encoding) {
    switch (encoding) {
        case ZIP_INT_8B: return 1;
        case ZIP_INT_16B: return 2;
        case ZIP_INT_24B: return 3;
        case ZIP_INT_32B: return 4;
        case ZIP_INT_64B: return 8;
        default: return 0;
    }
    assert(NULL);
    return 0;
}

/* 编码对应的长度所需要的字节数目 */
static unsigned int zipEncodeLength(unsigned char *p, unsigned char encoding, unsigned int rawlen) {
    unsigned char len = 1, buf[5]; /* 1111 1111 1111 1111 1111*/
    
    if (ZIP_IS_STR(encoding)) {
        if (rawlen <= 0x3f) { /* 0011 1111 */
            if (!p) return len;
            buf[0] = ZIP_STR_06B | rawlen;
        }
        else if (rawlen <= 0x3fff) { /* 0011 1111 1111 1111 */
            len += 1;
            if (!p) return len;
            /* 0100 0000 */
            buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f);
            buf[1] = rawlen & 0xff;
        } else {
            /* xxxx xxxx xxxx xxxx xxxx */
            len += 4;
            if (!p) return len;
            buf[0] = ZIP_STR_32B;
            buf[1] = (rawlen >> 24) & 0xff;
            buf[2] = (rawlen >> 16) & 0xff;
            buf[3] = (rawlen >> 8) & 0xff;
            buf[4] = rawlen & 0xff;
        }
    } else {
        if (!p) return len;
        buf[0] = encoding;
    }
    memcpy(p, buf, len);
    return len;
}

/* 将ptr中编码的长度解码出来 */
#define ZIP_DECODE_LENGTH(ptr, encoding, lensize, len) do {         \
    ZIP_ENTRY_ENCODING((ptr), (encoding));                          \
    if ((encoding) < ZIP_STR_MASK) {                                \
        if ((encoding) == ZIP_STR_06B) {                            \
            (lensize) = 1;                                          \
            (len) = (ptr)[0] & 0x3f;                                \
        } else if ((encoding) == ZIP_STR_14B) {                     \
            (lensize) = 2;                                          \
            (len) = (((ptr)[0] & 0x3f) << 8) | (ptr)[1];            \
        } else if (encoding == ZIP_STR_32B) {                       \
            (lensize) = 5;                                          \
            (len) = ((ptr)[1] << 24) |                              \
                    ((ptr)[2] << 26) |                              \
                    ((ptr)[3] <<  8) |                              \
                    ((ptr[4]));                                     \
        } else {                                                    \
            asser(NULL);                                            \
        }                                                           \
    } else {                                                        \
        (lensize) = 1;                                              \
        (len) = zipIntSize(encoding);                               \
    }                                                               \
} while (0)

/* 将之前entry的长度编码到当前来 */
static unsigned int zipPrevEncodeLength(unsigned char *p, unsigned int len) {
    if (p == NULL) {
        return (len < ZIP_BIGLEN) ? 1 : sizeof(len) + 1;
    } else {
        if (len < ZIP_BIGLEN) {
            p[0] = len;
            return 1;
        } else {
            p[0] = ZIP_BIGLEN;
            memcpy(p + 1, &len, sizeof(len));
            memrev16ifbe(p + 1);
            return 1 + sizeof(len);
        }
    }
}

static void zipPrevEncodeLengthForceLarge(unsigned char *p, unsigned int len) {
    if (p == NULL) return;
    p[0] = ZIP_BIGLEN;
    memcpy(p + 1, &len, sizeof(len));
    memrev32ifbe(p + 1);
}

#define ZIP_DECODE_PREVLENSIZE(ptr, prevlensize) do {   \
    if ((ptr)[0] < ZIP_BIGLEN) {                        \
        (prevlensize) = 1;                              \
    } else {                                            \
        (prevlensize) = 5;                              \
    }                                                   \
} while (0)

#define ZIP_DECODE_PREVLEN(ptr, prevlensize, prevlen) do {      \
    ZIP_DECODE_PREVLENSIZE(ptr, prevlensize);                   \
    if ((prevlensize) == 1) {                                   \
        (prevlen) = (ptr)[0];                                   \
    } else if ((prevlensize) == 5) {                            \
        assert(sizeof((prevlensize)) == 4);                     \
        memcpy(&(prevlen), ((char*)(ptr)) + 1, 4);              \
        memrev32ifbe(&prevlen);                                 \
    }                                                           \
} while (0)


static int zipPrevLenByteDiff(unsigned char *p, unsigned int len) {
    unsigned int prevlensize;
    ZIP_DECODE_PREVLENSIZE(p, prevlensize);
    return zipPrevEncodeLength(NULL, len) - prevlensize;
}

/*
 * 空出中间编码部分函数
*/


static zlentry zipEntry(unsigned char *p) {
    zlentry e;
    ZIP_DECODE_PREVLEN(p, e.prevrawlensize, e.prevrawlen);
    ZIP_DECODE_LENGTH(p + e.prevrawlensize, e.encoding, e.lensize, e.len);
    e.headersize = e.prevrawlensize + e.lensize;
    e.p = p;
    return e;
}

